package DP.Lesson7;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/
 */
public class LIS {

    /**
     * dp[n] 表示 到第n个数字，最长的单调递增梳理
     * 那 dp[n] = dp[n-1] | n>n-1 +1
     * 有两个循环的
     */
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;if(n==0) return 0;

        int[] dp = new int[n];//base case就是自己，所以，不需要n+1
        Arrays.fill(dp, 1);//记得初始化这个 自己一定是子序列，所以，初始都是1
        for(int i=0; i<n; i++){
            //这里很关键是 j<i，再开一个循环，算当前j 有多少递增子序列长度，要重新算的
            for(int j=0;j<i; j++){//这是取每个数到i的最长递增
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }

        int res=Integer.MIN_VALUE;
        for(int i=0; i<n;i++){
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    /**
     * 增加二分查找，提升性能
     * dp[n] 表示 到第n个数字，最长的单调递增梳理
     * 二分的方式还没看明白，先跳过吧。。有点不好理解。
     */
    public int lengthOfLIS_search(int[] nums) {
        return 0;
    }

    public static void main(String[] args){
        int[] n = new int[]{-1,1,1,1};

    }


}
